//
// Created by LH on 2017/9/7.
//
#include <algorithm>
#include <iostream>
using namespace std;

int map[50][3];
int dis[50];
int n, m, start;
int flag;   //负权回路标记
int main()
{
    cin >> n >> m >> start;
    for (int t_init = 0; t_init <= n; t_init++)
    {
        dis[t_init] = 1e9;
    }
    for (int t_ipt = 1; t_ipt <= m; t_ipt++)
    {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        map[t_ipt][0] = t1;
        map[t_ipt][1] = t2;
        map[t_ipt][2] = t3;
    }
    dis[start] = 0;
    for (int fb1 = 1; fb1 < n; fb1++)
    {
        for (int fb2 = 1; fb2 <= m; fb2++)
        {
            dis[map[fb2][1]] = min(dis[map[fb2][1]], dis[map[fb2][0]] + map[fb2][2]);
        }
    }
    for (int t_test = 1; t_test <= m; ++t_test) {
        if (dis[map[t_test][0]] + map[t_test][2] < dis[map[t_test][1]])
        {
            flag = 1;
            break;
        }
    }
    if (flag)
    {
        cout << "本图含有负权回路!" << endl;
    }
    else
    {
        for (int t_pnt = 1; t_pnt <= n; t_pnt++)
        {
            cout << dis[t_pnt] << " ";
        }
    }
    return 0;
}

/*
//无负权回路数据
5 5 1
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
//有负权回路
5 6 1
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
2 1 -1
*/